package leetcode.code1488;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;


//执行用时：68 ms, 在所有 Java 提交中击败了45.57%的用户
//
//内存消耗：59.5 MB, 在所有 Java 提交中击败了17.05%的用户
//
//通过测试用例：80 / 80
public class Solution implements IDebug {

	public int[] avoidFlood(int[] rains) {
		int len = rains.length;
		int[] ans = new int[len];
		Map<Integer, Integer> full = new HashMap<>();
		TreeSet<Integer> ts = new TreeSet<>();
		for (int i = 0; i < len; i++) {
			int cur = rains[i];
			if (cur > 0) {
				ans[i] = -1;
				if (full.containsKey(cur)) {
					int fillDay = full.get(cur);
					Integer emp = ts.ceiling(fillDay);
					if (emp == null) {
						return new int[] {};
					} else {
						ans[emp] = cur;
						ts.remove(emp);
						full.put(cur, i);// 这个千万别忘啊
					}
				} else {
					full.put(cur, i);
				}
			} else {
				ans[i] = 1;
				ts.add(i);
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[-1,-1,-1,-1]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,2,3,4]")));

	}

	@Override
	public void debug2() {
		int[] e = HelpDebug.str2array3("[-1,-1,2,1,-1,-1]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,2,0,0,2,1]")));

	}

	@Override
	public void debug3() {
		int[] e = HelpDebug.str2array3("[]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,2,0,1,2]")));

	}

	@Override
	public void debug4() {
		int[] e = HelpDebug.str2array3("[]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[0,1,1]")));

	}

	public void debug5() {
		int[] e = HelpDebug.str2array3("[-1,1,-1,2,-1,-1]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,0,2,0,2,1]")));

	}

	public void debug6() {
		int[] e = HelpDebug.str2array3("[-1,1,-1,-1,2,-1,-1]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,0,2,3,0,1,2]")));

	}

	public void debug7() {
		int[] e = HelpDebug.str2array3("[-1,1,-1,2,-1,3,-1,2,1,1,-1,-1,-1]");
		HelpDebug.compare(e, this.avoidFlood(HelpDebug.str2array3("[1,0,2,0,3,0,2,0,0,0,1,2,3]")));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
